
# 21st of April 2010
#80 min.

import unittest

BRACKETS = "()[]{}<>"

def word(lst):
	s = ""
	for element in lst:
		s+=str(element)
	return s

opened = word([BRACKETS[i] for i in range(0, len(BRACKETS), 2)])
closed = word([BRACKETS[i] for i in range(1, len(BRACKETS), 2)])

def oddchars(string, listofopened, listofclosed):
	'''check that open and closed token are in same number'''
	string = str(string)
	assert(len(listofopened)==len(listofclosed))

	for i in range(len(listofopened)):
		ochar = listofopened[i]
		cchar = listofclosed[i]
		if string.count(ochar) != string.count(cchar):
			return False
	return True

def goodbrackets(string):
	'''takes a string with only BRACKETS and check if they are in correct balance'''
	if not string : 
		return False
	if not oddchars(string, opened, closed):
		return False

	# for each brackets create a stack, push if there is a open brakets, pop otherways.
	l = [ [] for i in opened ]
	for char in string:
		index = opened.find(char)
		if index != -1: 
			l[index].append(char)
		index = closed.find(char)
		if index != -1: 
			try: l[index].pop()
			except IndexError: return False

	# if stacks are empty string is in a good balance.
	llen = [len(l[i]) for i in range(len(l))]
	return not any(llen)

class test(unittest.TestCase):
	bads = ["",
		None,
		"(", 
		")", 
		"((",
		"(][)",
		"(<(>))"
		"[)()(]",
		"<>)(<>",
		#"{(<[>])()}"
		]
	goods = ["()",
		 "()()",
		 "[()()]",
		 "{[][[()<()>]]}",
		 "[<([])<>(()())>]"
		]

	def test(self):
		print("========= test bads")
		for test in self.bads: self.assertTrue(goodbrackets(test)==False)
		print("========= test goods")		
		for test in self.goods: self.assertTrue(goodbrackets(test)==True)

if __name__ == "__main__":
	unittest.main()


